package io.github.handyang.algorithms.graph;

import java.util.Collections;
import java.util.Stack;

public class DFSPaths implements Paths {
    private final Graph graph;
    //起点
    private final int s;

    private final int[] edgeTo;//起点到i路径上的最后一个点

    private final boolean[] marked;

    public DFSPaths(Graph graph, int s) {
        this.graph = graph;
        this.s = s;

        this.edgeTo = new int[graph.V()];
        this.marked = new boolean[graph.V()];
        dfs(s);
    }

    private void dfs(int startPoint) {
        marked[startPoint] = true;
        Iterable<Integer> adj = graph.adj(startPoint);

        for (Integer point : adj) {
            if (marked[point]) continue;

            edgeTo[point] = startPoint;
            dfs(point);
        }
    }

    @Override
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return Collections.emptyList();

        Stack<Integer> res = new Stack<>();
        for (int w = v; w != s; w = edgeTo[w]) {
            res.push(w);
        }
        res.push(s);
        return res;
    }
}
